Cloud data storage is swiftly supplanting many forms of local storage for consumers and enterprises alike. Cloud storage providers have an interest in demonstrating that files in their custody enjoy strong confidentiality and other protections, both to differentiate their services and to ease regulatory compliance for their clients.
For example, security breach notification laws in the United States, such as those in the recently-enacted HITECH (Health Information Technology for Economic and Clinical Health) Act, typically include a safe harbor exemption for encrypted data. To benefit from such provisions, cloud storage providers must demonstrate at a minimum that while in storage, files are in encrypted form. See M. Burdon et al., “Encryption safe harbours and data breach notification laws,” Computer Law & Security Review, 26(5):520-534, 2010.
Auditors today commonly rely on periodic facility inspections and system architecture and configuration reviews to verify compliance with data-handling requirements under established standards such as Statement on Auditing Standards (SAS) No. 70. Such approaches are expensive and error prone. They do not support continuous monitoring or extensive fine-grained inspection and often presume correct reduction of security policies to practice. Automated verification of stored file formats is thus a compelling alternative or supplement to traditional audit approaches. To maximize cost effectiveness and minimize trust assumptions in an audited cloud storage provider, such verification should be executable remotely, e.g., by an auditor over the Internet.
Verifying that a file is encrypted would be much easier for an auditor or client that had sole possession of the encryption keys. In order for a cloud storage provider to compute over stored, encrypted data and furnish plaintext on demand, however, the provider itself must encrypt the file and manage the keys. This is the most common cloud storage model and the one that burdens clients the least. Furthermore, for a cloud storage provider to assume responsibility for file confidentiality and minimize security requirements for clients, it should never divulge encryption keys to external entities, the file owner included.
An auditor or client should therefore be able to verify that stored files are encrypted by a cloud storage provider that is itself managing the keys and performing the encryption and decryption operations on the files.
If the cloud storage provider holds encryption keys, then remotely verifying that stored files are encrypted presents a very difficult problem. Consider by way of example a client that entrusts a cloud storage provider with file F, asking that the cloud storage provider store it encrypted under some secret key κ as ciphertext G. How can the client verify that the cloud storage provider is actually storing G and not F? The client might challenge the cloud storage provider at a random time to send it the ciphertext G. But the cloud storage provider could deceive the client by just sending a random string R. If the cloud storage provider claims to be using an appropriate encryption algorithm, such as one that is indistinguishable under chosen ciphertext attack (IND-CCA), the client will be unable to distinguish between the random string R and the ciphertext G. It is also possible for the cloud storage provider to deceive the client by storing F in unencrypted form and then computing G on the fly, only in response to a verification request from the client.
Accordingly, a need exists for techniques for verifying that files stored by cloud storage providers are subject to appropriate protections such as encryption.